package org.example.l0;

import org.junit.jupiter.api.Nested;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class nextPermutation {
    @Test
    void run() {
        int[] nums = {3, 2, 1};
        nextPermutation(nums);
        System.out.println(11);
    }

    public void nextPermutation(int[] nums) {
        int len = nums.length;
        int i = len - 2;
        for (; i >= 0 && nums[i] >= nums[i + 1]; i--) {
        }

        if (i >= 0) {
            int j = len - 1;
            for (; i >= 0 && j >= 0 && nums[i] >= nums[j]; j--) {
            }

            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        Arrays.sort(nums, i + 1, len);
    }

    @Nested
    class Solution {

        @Test
        void run() {
            int[] nums = {4, 5, 2, 6, 3, 1};
            nextPermutation(nums);
            System.out.println(11);
        }

        public void nextPermutation(int[] nums) {
            int i = nums.length - 2;
            while (i >= 0 && nums[i] >= nums[i + 1]) {
                i--;
            }
            if (i >= 0) {
                int j = nums.length - 1;
                while (j >= 0 && nums[i] >= nums[j]) {
                    j--;
                }
                swap(nums, i, j);
            }
            reverse(nums, i + 1);
        }

        public void swap(int[] nums,
                         int i,
                         int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        public void reverse(int[] nums,
                            int start) {
            int left = start, right = nums.length - 1;
            while (left < right) {
                swap(nums, left, right);
                left++;
                right--;
            }
        }
    }
}
